//#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//void _MergeSort(int* a, int begin, int end, int* tmp)
//{
//	if (begin == end)
//		return;
//	int mid = (begin + end) / 2;
//	//
//	_MergeSort(a, begin, mid, tmp);
//	_MergeSort(a, mid + 1, end, tmp);
//	int begin1 = begin, end1 = mid;
//	int begin2 = mid + 1, end2 = end;
//	int i = begin;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (a[begin1] <= a[begin2])
//		{
//			tmp[i++] = a[begin1++];
//		}
//		else
//		{
//			tmp[i++] = a[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		tmp[i++] = a[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		tmp[i++] = a[begin2++];
//	}
//	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
//}
//
//void MergeSort1(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc fail");
//	}
//	_MergeSort(a, 0, n - 1, tmp);
//	free(tmp);
//	tmp = NULL;
//}
//
//void MergeSort2(int* a, int n)
//{
//	int* tmp = (int*)malloc(sizeof(int) * n);
//	if (tmp == NULL)
//	{
//		perror("malloc fail");
//	}
//	int gap = 1;
//	while (gap < n)
//	{
//		for (int k = 0; k < n; k += 2 * gap)
//		{
//			int begin1 = k, end1 = begin1 + gap - 1;
//			int begin2 = end1 + 1, end2 = begin2 + gap - 1;
//			if (end1 >= n || begin2 >= n)
//				break;
//			if (end2 >= n)
//				end2 = n - 1;
//			int i = k;
//			while (begin1 <= end1 && begin2 <= end2)
//			{
//				if (a[begin1] <= a[begin2])
//				{
//					tmp[i++] = a[begin1++];
//				}
//				else
//				{
//					tmp[i++] = a[begin2++];
//				}
//			}
//			while (begin1 <= end1)
//			{
//				tmp[i++] = a[begin1++];
//			}
//			while (begin2 <= end2)
//			{
//				tmp[i++] = a[begin2++];
//			}
//			memcpy(a + k, tmp + k, sizeof(int) * (end2 - k + 1));
//		}
//		gap *= 2;
//	}
//	free(tmp);
//	tmp = NULL;
//}
//int main()
//{
//	int n = 10;
//	int arr[10] = {5,2,7,4,1,9,8,11,6,3};
//
//
//	MergeSort1(arr, n);
//	int j = 0;
//	for (j = 0; j < n; j++)
//	{
//		printf("%d ", arr[j]);
//	}
//	return 0;
//}
//
//#include <stdio.h>
//int main() 
//{ 
//	int N; 
//	scanf("%d", &N); 
//	int arr[N + 1]; 
//	for (int i = 0; i < N; i++) 
//	{ 
//		scanf("%d", &arr[i]); 
//	} 
//	int new_num; 
//	scanf("%d", &new_num); 
//	int inserted = 0; 
//	for (int i = 0; i < N; i++) 
//	{ 
//		if (new_num < arr[i]) { 
//			for (int j = N; j > i; j--) { 
//				arr[j] = arr[j - 1]; 
//			} 
//			arr[i] = new_num; 
//			inserted = 1; 
//			break;
//		} 
//	} 
//	if (!inserted) 
//	{
//		arr[N] = new_num;
//	} 
//	for (int i = 0; i < N + 1; i++) 
//	{ 
//		printf("%d", arr[i]);
//		if (i != N)
//		{
//			printf(" ");
//		} 
//	}
//	return 0;
//}